template <class ItemType>
BinaryTree<ItemType>::BinaryTree()
// Class constructor.
{
	root = NULL;
}

template <class ItemType>
BinaryTree<ItemType>::~BinaryTree()
// Class destructor.
{
	clearTree(root);
}

template <class ItemType>
BinaryTree<ItemType>::BinaryTree(const BinaryTree &orig)
//copy constructor
{
	copyTree(orig);
}

template <class ItemType>
BinaryTree<ItemType> BinaryTree<ItemType>::operator=(const BinaryTree<ItemType>& rhs)
//assignment operator
{
	if (this == &rhs)
		return *this;

	clearTree(root);
	copyTree(rhs);
	return *this;
}

template <class ItemType>
void BinaryTree<ItemType>::clearTree(NodeType<ItemType>* tree)
{
	if (tree == NULL)
		return;
	else 
	{
		clearTree(tree->left);
		clearTree(tree->right);
		delete tree;
	}
}

template <class ItemType>
void BinaryTree<ItemType>::copyTree(const BinaryTree<ItemType>& orig)
{
	root = NULL;
	if (orig.root == NULL)
		return;

	NodeType<ItemType>* sourcePtr;
	sourcePtr = orig.root;
	copy2(root, sourcePtr);
}

template <class ItemType>
void BinaryTree<ItemType>::copy2(NodeType<ItemType>*& current, NodeType<ItemType>* orig)
{
	if (orig != NULL)
	{
		current = new NodeType<ItemType>;
		current->info = orig->info;
		copy2(current->left, orig->left);
		copy2(current->right, orig->right);
	}	
	else
		current = NULL;
}

template <class ItemType>
void BinaryTree<ItemType>::Insert(ItemType value, string trail)
{
	if (trail == "root")
	{
		clearTree(root);
		root = new NodeType<ItemType>;
		root->info = value;
		root->left = NULL;
		root->right = NULL;
	}
	else
	{
		char next;
		NodeType<ItemType>* current = root;
		while (trail.size() > 1)
		{
			next = trail[0];
			if (next == 'R')
				current = current->right;
			else if (next == 'L')
				current = current->left;
			trail = trail.substr(1, trail.size() - 1);
		}
		if (trail[0] == 'R')
		{
			current->right = new NodeType<ItemType>;
			current = current->right;
		}
		else
		{
			current->left = new NodeType<ItemType>;
			current = current->left;
		}
		current->left = NULL;
		current->right = NULL;
		current->info = value;
	}
}


template <class ItemType>
void BinaryTree<ItemType>::PrintPre(ostream &out)
{
	PrintPre2(out, root);
	out << endl;
}

template <class ItemType>
void BinaryTree<ItemType>::PrintPre2(ostream& out, NodeType<ItemType>* current)
{
	if (current == NULL)
		return;
	out << current->info << ' ';
	PrintPre2(out, current->left);
	PrintPre2(out, current->right);
}


template <class ItemType>
void BinaryTree<ItemType>::PrintBottomToTop(ostream& out)
{
	if (root == NULL)
		return;
	queue<NodeType<ItemType>*> Q;
	stack<NodeType<ItemType>*> S;
	NodeType<ItemType>* current;
	
	Q.push(root);
	while (!Q.empty())
	{
		current = Q.front();
		Q.pop();
		S.push(current);
		if (current->right != NULL)
			Q.push(current->right);
		if (current->left != NULL)
			Q.push(current->left);
	}
	while (!S.empty())
	{
		current = S.top();
		S.pop();
		out << current->info;
		out << " ";
	}
	out << endl;
}

template <class ItemType>
bool BinaryTree<ItemType>::DeleteSubtreeAt(ItemType value)
{
	if (root == NULL)
		return false;
	if(root->info == value)
	{
		clearTree(root);
		root = NULL;
		return true;
	}
	return deleteSubTreeAt2(value, root);
}

template <class ItemType>
bool BinaryTree<ItemType>::deleteSubTreeAt2(ItemType value, NodeType<ItemType>* current)
{
	bool left = false;
	bool right = false;

	if (current->left == NULL && current->right == NULL)
		return false;
	if (current->left != NULL && current->left->info == value)
	{
		clearTree(current->left);
		current->left = NULL;
		return true;
	}
	if (current->right != NULL && current->right->info == value)
	{
		clearTree(current->right);
		current->right = NULL;
		return true;
	}
	if (current->left != NULL)
		left = deleteSubTreeAt2(value, current->left);
	if (current->right != NULL)
		right = deleteSubTreeAt2(value, current->right);

	return (left || right);
}

template <class ItemType>
bool BinaryTree<ItemType>::SiblingOf(ItemType value, ItemType &sibling)
{
	if (root == NULL)
		return false;

	return SiblingOf2(value, sibling, root);
}

template <class ItemType>
bool BinaryTree<ItemType>::SiblingOf2(ItemType value, ItemType& sibling, NodeType<ItemType>* current)
{
	bool left = false;
	bool right = false;

	if (current->right == NULL && current->left == NULL)
		return false;
	if (current->right != NULL && current->right->info == value)
	{
		if(current->left != NULL)
		{
			sibling = current->left->info;
			return true;
		}
		else
			return false;
	}
	if (current->left != NULL && current->left->info == value)
	{
		if (current->right != NULL)
		{
			sibling = current->right->info;
			return true;
		}
		else
			return false;
	}
	if (current->left != NULL)
		left = SiblingOf2(value, sibling, current->left);
	if (current->right != NULL)
		right = SiblingOf2(value, sibling, current->right);

	return (left || right);
}

template <class ItemType>
bool BinaryTree<ItemType>::InOrderNext(ItemType value, ItemType& next)
{
	if (root == NULL)
		return false;

	bool found = false;
	return inOrder2(value, next, root, found);
}

template <class ItemType>
bool BinaryTree<ItemType>::inOrder2(ItemType value, ItemType& next, NodeType<ItemType>* current, bool& found)
{
	if(current == NULL)
		return false;
	if (inOrder2(value, next, current->left, found))
		return true;
	if (found)
	{
		found = false;
		next = current->info;
		return true;
	}
	else if (current->info == value)
		found = true;

	return inOrder2(value, next, current->right, found);
}

template <class ItemType>
ItemType BinaryTree<ItemType>::RightmostOnLevel(int level)
{
	queue<NodeType<ItemType>*> Q;
	RightmostOnLevel2(Q, level, root, 0);
	return Q.front()->info;		
}

template <class ItemType>
void BinaryTree<ItemType>::RightmostOnLevel2(queue<NodeType<ItemType>*>& Q, int level, NodeType<ItemType>* current, int thisLevel)
{
	if (current == NULL)
		return;

	if (thisLevel == level)
	{
		Q.push(current);
		return;
	}
	RightmostOnLevel2(Q, level, current->right, thisLevel + 1);
	if(Q.size() == 0)
		RightmostOnLevel2(Q, level, current->left, thisLevel + 1);

}

template <class ItemType>
double BinaryTree<ItemType>::AvgLeafDepth()
{
	queue<int> Q;
	findLeaves(Q, root, 0);
	double count = 0;
	double sum = 0;
	while (!Q.empty())
	{
		sum += Q.front();
		Q.pop();
		count++;
	}
	return (sum / count);
}

template <class ItemType>
void BinaryTree<ItemType>::findLeaves(queue<int>& Q, NodeType<ItemType>* current, int level)
{
	if (current->left == NULL && current->right == NULL)
		Q.push(level);
	else
	{
		if (current->left != NULL)
			findLeaves(Q, current->left, level + 1);
		if (current->right != NULL)
			findLeaves(Q, current->right, level + 1);
	}
}